package com.sicheng.algorithm.node;

import lombok.AllArgsConstructor;
import lombok.Data;

/**
 * @author zsc
 * @version 1.0
 * @date 2021/9/24 8:27
 */
@Data
@AllArgsConstructor
public class LastChildren {

    public static void main(String[] args) {
        LastChildren children = new LastChildren(4, 4);
        System.out.println(children.lastChildren());
    }

    /**
     * 让小朋友们围成一个大圈。
     * 然后，随机指定一个数 m，让编号为 0 的小朋友开始报数。
     * 每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，
     * 并且不再回到圈中，从他的下一个小朋友开始，
     * 继续 0...m-1 报数 .... 这样下去 .... 直到剩下最后一个小朋友，可以不用表演。
     */
    private int m;
    private int totalChild;

    public int lastChildren() {
        return lastChildren(0);
    }

    public int lastChildren(int i) {
        ListNode head = initListNode(totalChild);

        if (head == null)
            return -1;
        while (totalChild > 0 && i < m) {

            if (i == m - 1) {
                removeChild(head);
                i = 0;
            }

            if (head.next == head) {
                break;
            }

            i++;
            head = head.next;

        }

        return head.val;

    }

    private ListNode initListNode(int totalChild) {
        if (totalChild <= 0)
            return null;

        ListNode head = new ListNode(0);

        if (totalChild > 1) {
            for (int i = 1; i < totalChild; i++) {
                ListNode node = new ListNode(i);
                ListNode.insertOnTail(head, node);
            }
        }

        ListNode tail = ListNode.getTail(head);

        tail.next = head;

        return head;
    }

    public void removeChild(ListNode node) {
        if (node == null || node == node.next)
            return;

        ListNode next = node.next;
        node.val = next.val;
        node.next = next.next;

        totalChild--;
    }

}
